package question11_15;

import java.util.zip.CheckedOutputStream;

/**
 * @description:  矩阵中的路径--->回溯
 * @author: jhy
 * @time: 2021/5/20 13:28
 */
public class Question12 {

    public static void main(String[] args) {

    }

    public boolean hasPath (char[][] matrix, String word) {

        //循环找到首个字母的初始位置
        for(int i = 0;i < matrix.length;i++){
            for(int j = 0;j < matrix[0].length;j++){
                //找到初始位置
                if(matrix[i][j] == word.charAt(0)){
                    //设立访问标记数组，每找到一个可能的初始位置，就要新创建一个访问标记数组
                    boolean[][] vis = new boolean[matrix.length][matrix[0].length];
                    //dfs传入参数：初始位置，访问标记数组，矩阵，寻找的字符位置，字符串
                    if(dfs(i,j,vis,matrix,0,word)){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public boolean dfs(int m,int n,boolean[][] vis,char[][] matrix,int k,String word){

        //如果m,n在矩阵外或者如果这一节点已经走过，返回false
        if(m < 0 || n < 0 || m >= matrix.length || n >= matrix[0].length
           || vis[m][n] == true){
            return false;
        }

        //如果这个位置的字母和字符串末尾的字母一样，且字符串序号就是最后一个，代表遍历结束，返回true
        if(matrix[m][n] == word.charAt(k) && k == word.length() - 1){
            return true;
        }

        //字符串字母是序号对应的字母
        if(matrix[m][n] == word.charAt(k)){
            //访问过了
            vis[m][n] = true;

            //递归 --->如果走的通，返回true
            if(dfs(m+1,n,vis,matrix,k+1,word) ||//向下走
               dfs(m,n+1,vis,matrix,k+1,word) || //向右走
               dfs(m-1,n,vis,matrix,k+1,word) || //向上走
               dfs(m,n-1,vis,matrix,k+1,word)){
                return true;
            }else {
                //走不通，记得将该点访问标志设为false，因为该点可能在后面被访问
                vis[m][n] = false;
                return false;
            }
        }else {
            //当前字符不是对应字母，返回false
            vis[m][n] = false;
            return false;
        }
    }
}
